package a12_SeqList.SingleLinkedList;

import a12_SeqList.ArrayList.SeqList;

/**
 * @Author quan
 * @Description 单链表的使用
 * @Date 2023/3/13 14:28
 */
/** 主要知道单链表是由节点组成的，有一个头结点，但是没有前驱。每个节点不仅存储自身的值，还保存指向下一个节点的地址值。最后一个节点的地址为Null。
 */
public class SingleLinkedList<E> implements SeqList<E> {
    private Node head;//定义头结点
    private int size;//定义节点的个数
    /**
     * 定义节点类:作为链表的私有内部类，对外部完全隐藏
     */
    private class Node{
        E val;//节点存储自身的值
        Node next;//节点存储下一节点的地址   ?  这个写法并不太懂
        //------------------------------------------------
        Node(E val){ //? 这里看不太懂：这个好像是一个构造方法
            this.val = val;
        }
    }
    /**
     * 个人感觉这里的数据处理操作主要分为三步：产生新的节点——>更改指向——>更新节点数
     * 链表中的关键在于找节点的前驱！而这里注意的一点就是头节点是没有前驱的。
     */

    /**
     * 头插：在当前链表头部添加元素
     */
    public void addFirst(E val) {
        //要插入一个元素，首先要产生一个新节点
        Node node = new Node(val);//将要添加的元素值添加到这个节点
        node.next = head;//新添加的节点的地址指向现有的头结点
        head = node;//更换现有的头结点：为新添加的这个节点
        size++;//添加的节点个数+1
    }
    /**
     * 尾插：增加值为element的节点
     * 思想：直接增加该值，则为尾插操作：size则表示元素的下一个位置
     */
    @Override
    public void add(E element) {
        add(size,element);//调用add方法,在size位置直接插入该值
    }
    /**
     * 增：在index位置插入值为element的元素
     *思想：判断要插入元素的Index位置是在链表的哪个位置？头插还是中间插入(找前驱)
     */
    @Override
    public void add(int index, E element) {
        //(1)判断索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("add index illegal");
        }
        //(2)判断索引插入的位置：如果是头插，直接调用头插方法
        if(index == 0){
            addFirst(element);
            return;
        }
        //(3)索引在中间正常位置下插入元素:找到索引位置的前驱，更改指向
        Node temp = head;
        //产生新节点
        Node node = new Node(element);
        //遍历链表，走到要添加节点的前驱
        for (int i = 0; i < index-1; i++) {
            temp = temp.next;
        }
        //记录被要增加节点的前驱
        Node prev = temp;
        //记录要增加节点的后一个节点
        Node next = prev.next;
        //更改指向
        prev.next = node;
        node.next = next;
        //(4)节点数加加
        size++;
    }
    /**
     * 删：删除索引位置上的值，并返回被删除的值
     * 思想：找被删除节点的前驱，更改节点的指向
     */
    @Override
    public E removeByIndex(int index) {
        //确定索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("remove index illegal");
        }
        //如果要删除的节点是头结点
        if(index == 0){
            Node node = head;
            head = node.next;
            node.next = null;
            size--;
            return node.val;
        }
        //用新的节点代替head不断向后移动
        Node prev = head;
        //遍历链表到被删除节点的前驱
        for (int i = 0; i < index-1; i++) {
            prev = prev.next;
        }
        //此时的prev就是被删除的节点的前驱
        Node node = prev.next;
        //记录被删除节点的值
        E removeVal = node.val;
        //更改节点的指向
        prev.next = node.next;
        node.next = null;
        //更改节点数
        size--;
        return removeVal;
    }
    /**
     * 删除第一个值为element的元素
     */
    @Override
    public void removeByValue(E element) {
        //特殊情况：头结点为Null
        if(head == null){
            return;
        }
        //如果删除的节点是头结点
        if(head.val.equals(element)){
            head = head.next;
            size--;
            return;
        }
        //如果删除的节点是在中间正常位置：遍历链表，判断链表中的节点是否与被删除的值相等
        Node prev = head;
        while (prev.next != null){
            if(prev.val.equals(element)){
                prev.next = prev.next.next;
                size--;
                return;
            }
            prev = prev.next;//不断移动
        }
        // 链表中没有待删除的节点
        System.out.println("当前链表中不存在值为" + element + "的节点");
    }
    /**
     * 删除所有值为element的元素:元素的删除还是比较难的，尤其是删除所有元素，情况比较复杂
     * 这里要注意指针的移动和边界条件的出现
     */
    @Override
    public void removeAllValue(E element) {
        //边界条件
        if(head == null){
            return;
        }
        //如果要删除的元素值在头结点且出现连续待删除的节点
        while (head !=null && head.val.equals(element)){
            head = head.next;
            size--;
        }
        //---------经过上面的删除头结点操作，如果此时整个链表已经不存在全部删除了
        if(head == null){
            return;
        }
        //正常位置的删除
        Node prev = head;
        while (prev.next != null){
            if(prev.next.val.equals(element)){
                //此时的prev就是被删除节点的前驱
                prev.next= prev.next.next;
                size--;
            }else{
                //----------只有当后继节点不是被删除的节点的时候才能移动prev引用
                prev=prev.next;
            }
        }
    }
    /**
     * 在索引为Index的位置插入元素elemnet
     */
    @Override
    public E set(int index, E elemnet) {
        //用一个节点表示head，不断移动
        Node node = head;
        //遍历集合，走到索引为Index的位置
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        //此时node节点就是要被设置新的值的节点
        //用一个变量接收旧值
        E oldVal = node.val;
        //设置新的值
        node.val = elemnet;
        //返回旧值
        return oldVal;
    }
    /**
     * 方法：索引的合法性判断
     */
    private boolean indexCheck(int index) {
        if(index<0 || index>size){
            return false;
        }else{
            return true;
        }
    }

    /**
     * 获取索引为index位置下的元素
     */
    @Override
    public E get(int index) {
        //用一个节点表示head，不断移动
        Node node = head;
        //遍历集合，走到索引为Index的位置
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        //此时node节点就是要被获取值的节点
        E getVal = node.val;
        return getVal;
    }
    /**
     *判断是否包含该元素
     */
    @Override
    public boolean contains(E element) {
        Node node = head;
        while (node.next != null){
            if(node.val.equals(element)){
                return true;
            }
            node = node.next;
        }
        return false;
    }
    /**
     * 返回元素的索引
     */
    @Override
    public int indexOf(E element) {
        //遍历链表，判断链表中的每个节点的元素值是否与传入的element值相等
        Node node = head;//用node代替head
        for (int i = 0; i < size; i++) {
            if(node.val.equals(element)){
                return i;
            }
            node = node.next;//不断移动到下一个节点
        }
        throw new IllegalArgumentException("没有找到该元素");
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        /**
         * 方法1：while循环方式
         */
        //链表中的最后一个元素的next地址为空
        //理论上：head是头结点，但是不能一直用head.next指向下一个节点，这样遍历完成,head就到了最后的节点，节点就没了
        //因此要用一个临时变量存储head
        Node temp = head;
        while (temp!=null){//说明该temp还没有遍历完节点，当前的节点还有值
            sb.append(temp.val);//将当前节点的值val添加到字符串容器中
            sb.append("——>");
            if(temp.next==null){
                sb.append("null");
            }
            temp= temp.next;//让temp指向下一个节点
        }
        /**
         * 方法2： for循环方式
         */
//        for (Node i = head; i !=null ; i=i.next) {
//            sb.append(i.val);//将当前节点的值val添加到字符串容器中
//            sb.append("——>");
//            if(i.next==null){
//                sb.append("null");
//            }
//        }
        return sb.toString();
    }
}
